#include "stack_queue.h"

/*------------------------------------*/

// 构造节点
listNode::listNode()
{
    this->next = NULL;
}

listNode::listNode(int nodeData, listNode *succ)
{
    this->data = nodeData;
    this->next = succ;
}

/*------------------------------------*/

void MyStack::printStack()
{
    listNode *p = topNode;

    while (p != NULL)
    {
        if (p->next == NULL)
            std::cout << p->data << std::endl;
        else
            std::cout << p->data << ",";

        p = p->next;
    }
}

MyStack::MyStack() // 创建栈
{
    this->topNode = NULL;
    this->stackSize = 0;
}

MyStack::~MyStack() // 清除栈内元素,销毁栈
{
    listNode *tempNode = topNode;
    while (tempNode != NULL)
    {
        listNode *nextNode = tempNode->next;
        delete tempNode;
        tempNode = nextNode;
    }
    stackSize = 0;
}

bool MyStack::push(const int &item) // 入栈,成功返回true,失败返回false
{
    listNode *newNode = new listNode(item, NULL);
    if (newNode == NULL)
    {
        return false;
    }
    newNode->next = this->topNode;
    this->topNode = newNode;
    this->stackSize++;
    return true;
}

bool MyStack::pop(int &item) // 出栈,成功返回true,失败返回false,出栈元素放在item
{
    if (this->topNode == NULL || this->stackSize <= 0)
    {
        return false;
    }
    listNode *tmpNode = this->topNode;
    item = tmpNode->data;
    this->topNode = tmpNode->next;
    delete tmpNode;
    this->stackSize--;
    return true;
}

void MyStack::pop() // 出栈
{
    listNode *tmpNode = this->topNode;
    this->topNode = tmpNode->next;
    delete tmpNode;
    this->stackSize--;
}

bool MyStack::getTop(int &item) // 获取栈顶,成功返回true,失败返回false,栈顶元素放在item
{
    if (this->topNode == NULL || this->stackSize <= 0)
    {
        return false;
    }
    item = this->topNode->data;
    return true;
}

int MyStack::getTop() // 获取栈顶
{
    int item = this->topNode->data;
    return item;
}


bool MyStack::isEmpty()
{
    if (this->topNode == NULL)
    {
        return true;
    }
    return false;
}

/*-----------------------------------------------*/

void MyQueue::printQueue()
{
    int cursor = front;

    while (cursor != rear)
    {
        if ((cursor + 1) % capacity == rear)
            std::cout << queue[cursor] << std::endl;
        else
            std::cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

MyQueue::MyQueue(const int &capacity) // 创建队列,容量为capacity
{
    this->capacity = capacity;
    this->front = 0;
    this->rear = 0;
    this->queue = new int[capacity];
}

MyQueue::~MyQueue() // 销毁队列
{
    delete[] this->queue;
}

bool MyQueue::enQueue(const int &val) // 入队,成功返回true,失败返回false
{
    if ((rear + 1) % capacity == front)
    {
        return false;
    }
    this->queue[rear] = val;
    this->rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int &item) // 出栈,成功返回true,失败返回false, 出队元素放在item
{
    if (rear == front)
    {
        return false;
    }
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int &item) // 获取队首,成功返回true,失败返回false,栈顶元素放在item
{
    if (rear == front)
    {
        return false;
    }
    item = queue[front];
    return true;
}

bool MyQueue::isFull()
{
    if ((rear + 1) % capacity == front)
    {
        return true;
    }
    return false;
}

bool isOperator(char c)
{
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

bool isNumber(char c)
{
    if (c >= '0' && c <= '9')
    {
        return true;
    }
    return false;
}

int precedence(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return 0;
}

/*中缀表达式转后缀表达式,转化成功返回true, 后缀表达式放在result中;*/
/*表达式错误返回false, 错误字符串Expression is wrong!放在result中*/
bool postfixExpression(const std::string &infix, std::string &result)
{
    MyStack s;
    result="";
    for (char c : infix) {
        if (isNumber(c)) {
            result += c;
        } else if (c == '(') {
            s.push(c);
        } else if (c == ')') {
            while (!s.isEmpty() && s.getTop()!= '(') {
                result += s.getTop();
                s.pop();
            }
            if (s.isEmpty()) {
                result = "Expression is wrong!";
                return false;
            }
            s.pop(); 
        } else if (isOperator(c)) {
            while (!s.isEmpty() && precedence(s.getTop()) >= precedence(c)) {
                result += s.getTop();
                s.pop();
            }
            s.push(c);
        } else {
            result = "Expression is wrong!";
            return false;
        }
    }
    while (!s.isEmpty()) {
        if (s.getTop() == '(') {
            result = "Expression is wrong!";
            return false;
        }
        result += s.getTop();
        s.pop();
    }
    return true;
}

/*表达式求值,表达式正确成功计算返回true,结果放在result中;*/
/*表达式错误计算不能完成返回false, result中放0*/
bool expressionVal(const std::string &expr, int &result)
{
    std::string postexpr;
    result = 0;
    bool flag = postfixExpression(expr, postexpr);
    if (flag)
    {
        MyStack opnd;
        for (auto ch : postexpr)
        {
            if (isdigit(ch))
            {
                int num = ch - '0';
                opnd.push(num);
            }else {
                int op1, op2;
                opnd.getTop(op2);
                opnd.pop();
                opnd.getTop(op1);
                opnd.pop();
                switch (ch)
                {
                    int res;
                    case '*': 
                        res = op1 * op2;
                        opnd.push(res);
                        break;
                    case '/': 
                        res = op1 / op2;
                        opnd.push(res);
                        break;
                    case '+': 
                        res = op1 + op2;
                        opnd.push(res);
                        break;
                    case '-': 
                        res = op1 - op2;
                        opnd.push(res);
                        break;
                    
                    default:
                        break;
                }
            }
        }
        opnd.getTop(result);
        return true;
    }
    return false;
}

/*输出杨辉三角*/
void yanghui(const int &size)
{
    MyQueue q(size + 3);
    q.enQueue(1);
    q.enQueue(1);

    int s = 0;
    for (int i = 1; i <= size; i++)
    {
        q.enQueue(0);
        for (int j = 1; j <= i + 2; j++)
        {
            int item;
            q.deQueue(item);
            q.enQueue(s + item);
            s = item;
            if (j < i + 1)
            {
                std::cout << s << ",";
            }
            else if (j == i + 1)
            {
                std::cout << s;
            }
        }
        std::cout << std::endl;
    }
}